package com.adee.algorithm.structure;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class Test001_Array {
    public static void main(String[] args) {
//        test();
        test1();
    }

    /*
    * 稀疏数组：当原数组有很多相同值的时候，就可以转为稀疏数组进行压缩，例如：
    * 0  0  0  22 0  0  15
    * 0  11 0  0  0  17 0
    * 0  0  0  -6 0  0  0
    * 0  0  0  0  0  39 0
    * 91 0  0  0  0  0  0
    * 0  0  28 0  0  0  0
    * 转为稀疏数组：
    *       行  列   值
    * [0]   6   7   8
    * [1]   0   3   22
    * [2]   0   6   15
    * [3]   1   1   11
    * [4]   1   5   17
    * [5]   2   3   -6
    * [6]   3   5   39
    * [7]   4   0   91
    * [8]   5   2   28
    *
    * 稀疏数组第一行的三个元素记录的是原数组的行数、列数、有效值个数，其余行记录的是各个有效值的行索引、列索引、值。
    *
    * */
    public static void test() {
        int[][] arr = {
                {0,0,0,22,0,0,15},
                {0,11,0,0,0,17,0},
                {0,0,0,-6,0,0,0},
                {0,0,0,0,0,39,0},
                {91,0,0,0,0,0,0},
                {0,0,28,0,0,0,0}
        };
        System.out.println("原始数组：");
        printArr(arr);
        System.out.println("稀疏数组：");
        int[][] sparseArr = toSparseArray(arr);
        printArr(sparseArr);
        System.out.println("恢复成原数组：");
        int[][] originalArr = toOriginalArray(sparseArr);
        printArr(originalArr);
    }

    // 原数组（假定原数组为矩形）转为稀疏数组
    public static int[][] toSparseArray(int[][] originArr) {
        // 假定非零为有效值
        if(originArr == null || originArr.length == 0) return null;
        int maxLen = originArr.length * originArr[0].length + 1;
        if(maxLen == 0) return null;
        int[][] arr = new int[maxLen][3];
        int cnt = 0; // 有效数的个数
        int cols = 0; // 列数
        int tempVal;
        int tempCols;
        // list.add(new int[]{originArr.length, 0, 0}); // 第一行放原数组的行数、列数、有效数个数
        for (int i = 0; i < originArr.length; i++) {
            tempCols = 0;
            for (int j = 0; j < originArr[i].length; j++) {
                if((tempVal = originArr[i][j]) != 0) {
                    ++cnt;
                    arr[cnt][0] = i;
                    arr[cnt][1] = j;
                    arr[cnt][2] = tempVal;
                }
                ++tempCols;
            }
            if(tempCols > cols) cols = tempCols;
        }
        arr[0][0] = originArr.length;
        arr[0][1] = cols;
        arr[0][2] = cnt;
        return Arrays.copyOf(arr, cnt+1);
    }

    // 稀疏数组还原为原数组
    public static int[][] toOriginalArray(int[][] sparseArr) {
        if(sparseArr == null || sparseArr.length == 0 || sparseArr[0].length == 0)
            return null;
        int rows = sparseArr[0][0];
        int cols = sparseArr[0][1];
        int cnt = sparseArr[0][2];
        int[][] arr = new int[rows][cols];
        for (int i = 1; i <= cnt; i++) {
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }

    public static void test1() {
        int[] arr1 = genSortedArr(10);
        System.out.println("数组1：");
        printArr(arr1);
        int[] arr2 = genSortedArr(10);
        System.out.println("数组1：");
        printArr(arr2);
        int[] merge = merge(arr1, arr2);
        System.out.println("合并后数组：");
        printArr(merge);
    }
    // 合并两个有序数组为一个新的有序数组
    public static int[] merge(int[] arr1, int[] arr2) {
        if (arr1 == null || arr1.length == 0) return arr2;
        if (arr2 == null || arr2.length == 0) return arr1;
        int i = 0, j = 0, len1 = arr1.length, len2 = arr2.length;
        int[] retArr = new int[len1 + len2];
        for (int k = 0; k < len1+len2; k++) {
            if(arr1[i] < arr2[j]) {
                retArr[k] = arr1[i];
                if(i == len1-1) { // arr1已遍历完
                    if(j < len2-1) { // 若arr2还有剩余
                        System.arraycopy(arr2, j, retArr, k+1, len2-j);
                    }
                    break;
                }
                i++;
            } else {
                retArr[k] = arr2[j];
                if(j == len2-1) { // arr2已遍历完
                    if(i < len1-1) { // 若arr1还有剩余
                        System.arraycopy(arr1, i, retArr, k+1, len1-i);
                    }
                    break;
                }
                j++;
            }

        }


        return retArr;
    }

    public static int[] genSortedArr(int len) {
        int[] arr = new int[len];
        ThreadLocalRandom r = ThreadLocalRandom.current();
        for (int i = 0; i < len; i++) {
            arr[i] = r.nextInt(100);
        }
        // 排序
        int tmp;
        for (int i = len-1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]) {
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }

        return arr;
    }

    public static void printArr(Integer[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
